class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class CopyRandomList {
    public static Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // 第一步：复制每个节点并插入到原节点后面
        Node current = head;
        while (current != null) {
            Node newNode = new Node(current.val);
            newNode.next = current.next;
            current.next = newNode;
            current = newNode.next;
        }

        // 第二步：设置新节点的random指针
        current = head;
        while (current != null) {
            if (current.random != null) {
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }

        // 第三步：拆分链表
        Node oldHead = head;
        Node newHead = head.next;
        Node currentOld = oldHead;
        Node currentNew = newHead;

        while (currentOld != null) {
            currentOld.next = currentNew.next;
            currentOld = currentOld.next;
            if (currentOld != null) {
                currentNew.next = currentOld.next;
                currentNew = currentNew.next;
            } else {
                currentNew.next = null; // 确保新链表的最后一个节点的next为null
            }
        }

        return newHead;
    }

    // 辅助方法：创建测试链表
    public static Node createTestList() {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);

        node1.next = node2;
        node2.next = node3;

        node1.random = node3;
        node2.random = node1;
        node3.random = node2;

        return node1;
    }

    // 辅助方法：打印链表（包括随机指针）
    public static void printList(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print("Node " + current.val + ": next = ");
            if (current.next != null) {
                System.out.print(current.next.val);
            } else {
                System.out.print("null");
            }

            System.out.print(", random = ");
            if (current.random != null) {
                System.out.println(current.random.val);
            } else {
                System.out.println("null");
            }
            current = current.next;
        }
    }

    public static void main(String[] args) {
        // 创建测试链表
        Node original = createTestList();

        System.out.println("原始链表:");
        printList(original);

        // 执行深拷贝
        Node copy = copyRandomList(original);

        System.out.println("\n复制链表:");
        printList(copy);

        // 验证深拷贝是否正确
        System.out.println("\n验证深拷贝:");
        Node currOriginal = original;
        Node currCopy = copy;

        boolean isCorrect = true;
        while (currOriginal != null && currCopy != null) {
            // 验证值相同但不是同一个对象
            if (currOriginal == currCopy || currOriginal.val != currCopy.val) {
                isCorrect = false;
                break;
            }

            // 验证随机指针指向正确的复制节点
            if ((currOriginal.random == null && currCopy.random != null) ||
                    (currOriginal.random != null && currCopy.random == null)) {
                isCorrect = false;
                break;
            }

            if (currOriginal.random != null) {
                // 获取原始链表中随机指针指向的节点在链表中的位置
                Node tempOriginal = original;
                Node tempCopy = copy;
                int pos = 0;

                while (tempOriginal != currOriginal.random && tempOriginal != null) {
                    tempOriginal = tempOriginal.next;
                    tempCopy = tempCopy.next;
                    pos++;
                }

                if (tempOriginal == null || currCopy.random != tempCopy) {
                    isCorrect = false;
                    break;
                }
            }

            currOriginal = currOriginal.next;
            currCopy = currCopy.next;
        }

        // 验证两个链表长度相同
        if (currOriginal != null || currCopy != null) {
            isCorrect = false;
        }

        System.out.println("深拷贝是否正确: " + (isCorrect ? "是" : "否"));
    }
}